package main;

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        // 示例输入：方程系数和目标值（支持小数）
        double[] coefficients = {1/20.0, 1/33.0, 1/20.0}; // n1, n2, n3...
        double[] coefficients1 = { 7, 10, 1};
        double target = 1;                          // a
//        double[] coefficients = {33, 20, 99}; // n1, n2, n3...
//        double[] coefficients1 = { 7, 10, 1};
//        double target = 660;
//        1 * x /20  + 1 * y / 33  + 3 * z / 20 < 1
//        1 * 8 /20  + 1 * 10 / 33  + 3 * 1 / 20 < 1
        solveMaximalSolutions(coefficients, coefficients1, target);
    }

    public static void solveMaximalSolutions(double[] n, double[] n2, double a) {
        final int SCALE = 1000; // 小数精度控制（三位小数）
        int k = n.length;

        // 1. 检查输入合法性
        for (double ni : n) {
            if (ni < 0.001) {
                System.out.println("错误：所有系数必须 ≥ 0.001");
                return;
            }
        }

        // 2. 转换为整数问题（放大 SCALE 倍）
        int[] N = new int[k];
        int sumMin = 0;
        for (int i = 0; i < k; i++) {
            N[i] = (int) Math.round(n[i] * SCALE);
            sumMin += N[i]; // 每个变量取最小值 xi=1 时的总和
        }

        int A = (int) Math.round(a * SCALE);
        if (A <= sumMin) {
            System.out.println("无解：变量取最小值时已不满足不等式");
            return;
        }
        int A_prime = A - sumMin;

        // 3. 动态规划求解（转换为非负整数问题）
        Map<Integer, List<int[]>> dp = new HashMap<>();
        dp.put(0, new ArrayList<>());
        dp.get(0).add(new int[k]); // 初始解：所有 xi' = 0（对应 xi=1）

        for (int i = 0; i < k; i++) {
            int Ni = N[i];
            Map<Integer, List<int[]>> newDp = new HashMap<>();

            for (Map.Entry<Integer, List<int[]>> entry : dp.entrySet()) {
                int currentSum = entry.getKey();
                List<int[]> combs = entry.getValue();

                for (int[] comb : combs) {
                    int maxM = (A_prime - 1 - currentSum) / Ni; // 最大可添加次数
                    for (int m = 0; m <= maxM; m++) {
                        int newSum = currentSum + m * Ni;
                        int[] newComb = Arrays.copyOf(comb, k);
                        newComb[i] += m;

                        if (newSum >= A_prime) continue;

                        if (!newDp.containsKey(newSum)) {
                            newDp.put(newSum, new ArrayList<>());
                        }
                        newDp.get(newSum).add(newComb);
                    }
                }
            }
            dp = newDp;
        }

        // 4. 收集所有严格小于 A_prime 的解
        List<int[]> solutions = new ArrayList<>();
        for (Map.Entry<Integer, List<int[]>> entry : dp.entrySet()) {
            if (entry.getKey() < A_prime) {
                solutions.addAll(entry.getValue());
            }
        }

        // 5. 过滤极大解：至少存在一个变量加 1 后总和 ≥ A_prime
        List<int[]> maximalSolutions = new ArrayList<>();
        for (int[] comb : solutions) {
            boolean isMaximal = false;
            for (int i = 0; i < k; i++) {
                int tempSum = 0;
                for (int j = 0; j < k; j++) {
                    tempSum += (j == i) ? N[j] * (comb[j] + 1) : N[j] * comb[j];
                }
                if (tempSum >= A_prime) {
                    isMaximal = true;
                    break;
                }
            }
            if (isMaximal) {
                maximalSolutions.add(comb);
            }
        }

        // 6. 转换为原始变量并输出
        if (maximalSolutions.isEmpty()) {
            System.out.println("无满足条件的解");
        } else {
            System.out.println("满足条件的解（共 " + maximalSolutions.size() + " 种）：");
            for (int[] comb : maximalSolutions) {
                System.out.print("x = [");
                boolean res = true;
                for (int i = 0; i < k; i++) {
                    System.out.print((comb[i] + 1) + (i < k - 1 ? ", " : ""));
                    if((comb[i] + 1) < n2[i]){
                        res = false;
                    }
                }
                System.out.println("]"+(res ? "OK":"NO"));
            }
        }
    }

}